package sol.leetcode;


/**
 * Super Ugly Number
 */
public class Issue313 {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] found = new int[n];
        found[0] = 1;
        int[] index = new int[primes.length];//用于记录每个素数对应的丑数坐标，这个丑数乘以这个素数大于当前found中的最大数

        for (int i = 1; i < n; ++i) {
            //计算下一个丑数
            int nextUgly = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; ++j)
                nextUgly = Math.min(nextUgly, primes[j] * found[index[j]]);
            found[i] = nextUgly;

            //更新每个素数对应的下标
            for (int j = 0; j < primes.length; ++j) {
                int prime = primes[j];
                while (found[index[j]] * prime <= nextUgly)
                    index[j]++;
            }
        }

        return found[n - 1];
    }

    public static void main(String[] args) {
        int[] primes = {2, 7, 13, 19};
        int n = 12;
        Issue313 sol = new Issue313();

        System.out.println(sol.nthSuperUglyNumber(n, primes));
    }
}
